import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Four_Five {

	public static void main(String[] args) {
		 Integer[] list=new Integer[5];
	      list[0]=4654;
	      list[1]=6;
	      list[2]=97987;
	      list[3]=3;
	      list[4]=6;
	      DoublyLinkedList<Integer> a=new DoublyLinkedList<Integer>(list);
	      a.append(54);
	      a.append(369);//往最后两个添加元素
	      a.remove(6);
	      a.remove(5);//把最后两个删除
	      a.showList();//showlist，这里是双链表所以从前往后一次，从后往前一次
	      System.out.println(a.get(4));//得到第四个元素
	      a.set(2, 666);//把第二个元素设置为666
	      a.showList();
	     
	      

	}

}
class DoublyLinkedList<T extends Comparable> implements LList{
	
	
	int size=0;
	DNode<T> head=new DNode<T>();
	
	
	
	 public DoublyLinkedList(T[] element) {
			
			List list=new ArrayList<T>();
			for(int i=0;i<element.length;i++) {
				list.add(element[i]);
			}
			Collections.sort(list);
			DNode<T> p=this.head;
		    for(int i=0;i<list.size();i++) {
		    	DNode<T> node=new DNode<T>((T) list.get(i),null,null);
		    	p.next=node;
		    	node.prev=p;
		    	p=p.next;
		    	size++;
		    }
			
		}

	@Override
	public boolean isEmpty() {
	    if(this.size==0)
		return false;
	    
	    return true;
	}

	@Override
	public int length() {
		// TODO 自动生成的方法存根
		return this.size;
	}

	@Override
	public T get(int i) {
		
		if(i<0||i>this.size){
			return null;
		}
		
		DNode<T> p=this.head;
		for(int j=0;j<i;j++) {
			p=p.next;
		}
		
		return p.next.data;
		
	}

	@Override
	public boolean set(int i, Comparable x) {
		if(i>this.size||i<0)
			return false;
		DNode<T> p=this.head;
		for(int j=0;j<i;j++) {
			p=p.next;
		}
	   
	    p.data=(T)x;
	    
	    
	    return true;
	}

	@Override
	public boolean insert(int i, Comparable x) {
		if (i > this.size || i < 0)
			return false;
		DNode<T> p = this.head;
		for (int j = 0; j<i-1; j++) {
			p = p.next;
		}

		DNode<T> node = new DNode<T>((T) x, null,null);
		node.next=p.next;
		p.next.prev=node; 
		node.prev=p;
		p.next=node;
		
        size++;
		return true;
	}

	@Override
	public void append(Comparable x) {
		int i=this.size;
		DNode<T> p=this.head;
		for(int j=0;j<i;j++) {
			p=p.next;
		}
		DNode<T>node=new DNode<T>((T)x,null,null);
		p.next=node;
		node.prev=p;
		size++;
	}

	@Override
	public Comparable remove(int i) {
		if(i>this.size||i<0)
			return false;
		DNode<T> p=this.head;
		for(int j=0;j<i;j++) {
			p=p.next;
		}
		DNode<T> node=p.next;
		if(i!=this.size-1) {
		p.next.next.prev=p;
		p.next=p.next.next;
		}
		else {
			p.next=null;
		}
		size--;
		return node;
		
		
	}

	@Override
	public void removeAll() {
		this.head=new DNode<T>();
		
	}

	@Override
	public Comparable search(Comparable key) {
		DNode<T> p=this.head;
		for(int i=0;i<this.size;i++) {
			p=p.next;
			if(p.data.compareTo(key)==0) {
				return p;
			}
		}
			
		
		return null;
	}
	
	 public void showList() {
		    DNode<T> p=this.head;
			for(int i=0;i<this.size;i++) {
				System.out.print(p.next.data+" ");
				p=p.next;
			}
			System.out.println();
			for(int i=0;i<this.size;i++) {
				System.out.print(p.data+" ");
				p=p.prev;
			}
			System.out.println();
		}
	
}